<html>
  <head>
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
    <meta http-equiv="Content-Language" content="en" />
    <title>skalibs: the biguint library interface</title>
    <meta name="Description" content="skalibs: the biguint library interface" />
    <meta name="Keywords" content="skalibs biguint libbiguint library interface" />
    <!-- <link rel="stylesheet" type="text/css" href="//skarnet.org/default.css" /> -->
  </head>
<body>

<p>
<a href="../libskarnet.html">libskarnet</a><br />
<a href="../index.html">skalibs</a><br />
<a href="//skarnet.org/software/">Software</a><br />
<a href="//skarnet.org/">www.skarnet.org</a>
</p>

<h1> The <tt>biguint</tt> library interface </h1>

<p>
<tt>biguint</tt> is set of simple primitives performing arithmetical
operations on (unsigned) integers of arbitrary length. It is nowhere
near as powerful or efficient as specialized,
assembly language-optimized libraries such as
<a href="http://gmplib.org/">GMP</a>, but it has the advantages
of smallness and simplicity.
</p>

<h2> Compiling </h2>

<ul>
 <li> Use <tt>#include &lt;skalibs/biguint.h&gt;</tt> </li>
</ul>

<h2> Programming </h2>

<p>
 You should refer to the <tt>skalibs/biguint.h</tt> header for the exact function
prototypes.
</p>

<h3> <a name="defs" />
Definitions </h3>

<ul>
 <li> A <em>biguint</em> <tt>x</tt> is a pointer to an array <tt>u</tt>
of uint32_t, together with an unsigned integer <tt>n</tt> called its <em>length</em>.
<br><tt>x = (2^32)^0 * u[0] + (2^32)^1 * u[1] + ... + (2^32)^(n-1) * u[n-1]</tt>. </li>
 <li> Every <tt>u[i]</tt> is called a <em>limb</em>. </li>
 <li> The greatest integer <tt>i</tt> lesser than <tt>n</tt> for which
<tt>u[i]</tt> is non-zero is called the <em>order</em> of <tt>x</tt>. The
order of zero is 0. </li>
</ul>

<h3> <a name="basic" />
Basic operations </h3>

<h4> Creating a biguint </h4>

<p>
 Just declare <tt>uint32_t x[n] ;</tt> - <em>n</em> being the length of the
biguint. You could also allocate <em>x</em> in the heap, possibly using a
uint32_t <a href="../libstddjb/genalloc.html">genalloc</a>. In the following,
a biguint is always referred to as a <tt>uint32_t *</tt> with its
<tt>unsigned int</tt> length ; it must always be pre-allocated.
</p>

<p>
 If an operation fails because a biguint's length <tt>n</tt> is too small to
accommodate the result, the function will write the first (i.e. least significant)
<tt>n</tt> limbs of the result, truncating it, then return 0 with errno set to
EOVERFLOW.
</p>

<h4> Setting it to zero </h4>

<pre>
uint32_t *x ;
unsigned int n ;

 bu_zero(x, n) ;
</pre>

<p>
<tt>bu_zero()</tt> sets the first <tt>n</tt> limbs of <tt>x</tt> to zero.
</p>

<h4> Copying a biguint </h4>

<pre>
uint32_t const *x ;
unsigned int xn ;
uint32_t *y ;
unsigned int yn ;

  bu_copy(y, yn, x, xn) ;
</pre>

<p>
<tt>bu_copy()</tt> copies <tt>x</tt> to <tt>y</tt>, setting higher limbs of <tt>y</tt>
to zero if needed. It then returns 1. If <tt>y</tt> is too small to contain <tt>x</tt>,
the function returns 0 EOVERFLOW.
</p>

<h4> Calculating the order </h4>

<pre>
uint32_t const *x ;
unsigned int n ;
unsigned int r ;

  r = bu_len(x, n) ;
</pre>

<p>
<tt>bu_len()</tt> outputs the order of <tt>x</tt> of length <tt>n</tt>.
<tt>0&nbsp;&lt;=&nbsp;r&nbsp;&lt;=&nbsp;n</tt>.
</p>

<h4> Comparing two biguints </h4>

<pre>
uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
int r ;

  r = bu_cmp(a, an, b, bn) ;
</pre>

<p>
<tt>bu_cmp()</tt> returns -1 if <tt>a&nbsp;&lt;&nbsp;b</tt>, 1 if
<tt>a&nbsp;&gt;&nbsp;b</tt>, and 0 if <tt>a&nbsp;=&nbsp;b</tt>.
</p>

<h3> <a name="io" />
I/O operations </h3>

<h4> Writing a biguint as an array of bytes </h4>

<pre>
char *s ;
uint32_t const *x ;
unsigned int n ;

  bu_pack(s, x, n) ;
  bu_pack_big(s, x, n) ;
</pre>

<p>
<tt>bu_pack()</tt> writes <tt>4*n</tt> bytes to <tt>s</tt>. The bytes
are a little-endian representation of <tt>x</tt>.<br />
<tt>bu_pack_big()</tt> is the same, with a big-endian representation.
</p>

<h4> Reading a biguint from an array of bytes </h4>

<pre>
char const *s ;
uint32_t *x ;
unsigned int n ;

  bu_unpack(s, x, n) ;
  bu_unpack_big(s, x, n) ;
</pre>

<p>
<tt>bu_unpack()</tt> reads <tt>4*n</tt> little-endian bytes from <tt>s</tt>
and writes them into the corresponding biguint <tt>x</tt>. <br />
<tt>bu_unpack_big()</tt> is the same, but the bytes are interpreted as
big-endian.
</p>

<h4> Formatting a biguint for readable output </h4>

<pre>
char *s ;
uint32_t const *x ;
unsigned int n ;

  bu_fmt(s, x, n) ;
</pre>

<p>
<tt>bu_fmt()</tt> writes <tt>x</tt> in <tt>s</tt> as a standard big-endian
hexadecimal number. <tt>x</tt> is considered of length <tt>n</tt>, so
<tt>8*n</tt> bytes will be written to <tt>s</tt>, even if it <tt>x</tt>
starts with zeros. <tt>bu_fmt</tt> returns the number of bytes written.
</p>

<h4> Reading a biguint from readable format </h4>

<pre>
char const *s ;
uint32_t *x ;
unsigned int xn ;
unsigned int z ;
unsigned int len ;

  len = bu_scanlen(s, &amp;z) ;
  bu_scan(s, len, x, xn, z) ;
</pre>

<p>
 bu_scanlen() scans <tt>s</tt> for a biguint written as a hexadecimal
number and returns the number of
bytes read. The reading stops at the first byte encountered that is not
in the 0-9, A-F or a-f range. The <tt>z</tt> integer then contains the
number of bytes excluding leading zeros.
</p>

<p>
 If x has not been allocated yet, you can use <tt>xn = bitarray_div8(z)</tt>
(if you have included the <tt>bitarray.h</tt> header)
and allocate <tt>x</tt> with length <tt>xn</tt>.
</p>

<p>
<tt>bu_scan()</tt> then reads <tt>len</tt> bytes from <tt>s</tt>, assuming
there are <tt>z</tt> significant bytes (i.e. not leading zeros); it writes
the resulting biguint into <tt>x</tt> of length <tt>xn</tt>. It returns 1,
except if <tt>xn</tt> is too small, in which case it returns 0 EOVERFLOW.
</p>

<h3> <a name="arith" />
Arithmetic operations </h3>

<h4> Addition </h4>

<pre>
uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *c ;
unsigned int cn ;
unsigned char carrybefore ;
unsigned char carryafter ;

  bu_add(c, cn, a, an, b, bn) ;
  bu_sub(c, cn, a, an, b, bn) ;
</pre>

<p>
<tt>bu_add()</tt> adds <tt>a</tt> and <tt>b</tt>, and puts the result
into <tt>c</tt>. It returns 1 unless it has to truncate it.
</p>

<p>
<tt>bu_sub()</tt> substracts <tt>b</tt> from <tt>a</tt>, and puts the
result into <tt>c</tt>. If the result should be negative, then it is
written as <tt>(2^32)^cn - c</tt> and the function returns 0 EOVERFLOW.
</p>

<h4> Multiplication </h4>

<pre>
uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *c ;
unsigned int cn ;

 bu_mul(c, cn, a, an, b, bn) ;
</pre>

<p>
<tt>bu_mul()</tt> computes <tt>c=a*b</tt>.
Make sure that <tt>cn</tt> &ge; <tt>bu_len(a, an) + bu_len(b, bn)</tt>.
If it is not the case, the result will be truncated and bu_mul will return
0 EOVERFLOW.
</p>

<h4> Division </h4>

<pre>
uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *q ;
unsigned int qn ;
uint32_t *r ;
unsigned int rn ;

 bu_div(a, an, b, bn, q, qn, r, rn) ;
 bu_mod(r, rn, b, bn) ;
</pre>

<p>
<tt>bu_div()</tt> computes <tt>q</tt>, the quotient, and <tt>r</tt>, the
remainder, of <tt>a</tt> divided by <tt>b</tt>. If <tt>b</tt> is zero, it
returns 0 EDOM. If <tt>qn</tt> or <tt>rn</tt> is to small to store the
quotient or the remainder, it returns 0 EOVERFLOW.
<tt>bu_mod()</tt> computes only the remainder, and stores it in-place.
</p>

<h4> GCD </h4>

<pre>
uint32_t *r ;
unsigned int rn ;
uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;

 bu_gcd(r, rn, a, an, b, bn) ;
</pre>

<p>
</p>
<tt>bu_gcd()</tt> computes the greatest common divisor between <tt>a</tt>
and <tt>b</tt>, and stores it into <tt>r</tt>. It returns 1 if all went well.
</p>

<p>
 Note that this function iterates on divisions, so it might use a non totally
negligible amount of CPU time.
</p>


<h4> Left-shifts and right-shifts </h4>

<pre>
uint32_t *x ;
unsigned int xn ;
unsigned char carryafter ;
unsigned char carrybefore ;

 carryafter = bu_slbc(x, xn, carrybefore) ;
 carryafter = bu_srbc(x, xn, carrybefore) ;
</pre>

<p>
<tt>bu_slbc()</tt> computes <tt>x&nbsp;&lt;&lt;=&nbsp;1</tt>.
The least significant bit of <tt>x</tt> is then set to
<tt>carrybefore</tt>. <tt>bu_slbc()</tt> returns the
previous value of <tt>x</tt>'s most significant bit. <br />
<tt>bu_srbc()</tt> computes <tt>x&nbsp;&gt;&gt;=&nbsp;1</tt>.
The most significant bit of <tt>x</tt> is then set to
<tt>carrybefore</tt>. <tt>bu_slbc()</tt> returns the
previous value of <tt>x</tt>'s least significant bit.<br />
<tt>bu_slb(x, n)</tt> and <tt>bu_srb(x, n)</tt> are macros for
respectively <tt>bu_slbc(x, n, 0)</tt> and <tt>bu_srbc(x, n, 0)</tt>.
</p>

<h4> Modular operations </h4>

<pre>
uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *c ;
unsigned int cn ;
uint32_t const *m ;
unsigned int mn ;

 bu_addmod(c, cn, a, an, b, bn, m, mn) ;
 bu_submod(c, cn, a, an, b, bn, m, mn) ;
 bu_mulmod(c, cn, a, an, b, bn, m, mn) ;
 bu_divmod(c, cn, a, an, b, bn, m, mn) ;
 bu_invmod(c, cn, m, mn) ;
</pre>

<p>
<tt>bu_addmod()</tt> computes <tt>c&nbsp;=&nbsp;(a+b)&nbsp;mod&nbsp;m</tt>.<br />
<tt>bu_submod()</tt> computes <tt>c&nbsp;=&nbsp;(a-b)&nbsp;mod&nbsp;m</tt>.<br />
<tt>bu_mulmod()</tt> computes <tt>c&nbsp;=&nbsp;(a*b)&nbsp;mod&nbsp;m</tt>.<br />
<tt>a</tt> and <tt>b</tt> must already be numbers modulo <tt>m</tt>.<br />
The functions return 1 if all went well.
</p>

<p>
<tt>bu_divmod()</tt> computes <tt>a</tt> divided by <tt>b</tt> modulo
<tt>m</tt> and stores it into <tt>c</tt>. <br />
<tt>bu_invmod()</tt> computes the inverse of <tt>c</tt> modulo <tt>m</tt>
and stores it into <tt>c</tt>. <br />
The divisor and <tt>m</tt> must be relatively prime, else
those functions return 0 EDOM. <br />
 The algorithm for modular division and inversion is due to
<a href="http://research.sun.com/techrep/2001/abstract-95.html">Sheueling
Chang Shantz</a>.
</p>

</body>
</html>
